class Solution {
public:
    bool dfs(vector<vector<char>>& board,string word,vector<vector<char>>& visited,int cur,int x,int y){
        int m=board.size();
        int n=board[0].size();
        if(cur==word.length())
            return true;
        else if(x<0||y<0||x>=m||y>=n)
            return false;
        else if(word[cur]==board[x][y]&&visited[x][y]=='0'){
            visited[x][y]='1';
            bool ret=dfs(board,word,visited,cur+1,x-1,y)||dfs(board,word,visited,cur+1,x+1,y)
            ||dfs(board,word,visited,cur+1,x,y-1)||dfs(board,word,visited,cur+1,x,y+1);
            visited[x][y]='0';
            return ret;
        }
        else
            return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size();
        int n=board[0].size();
        vector<vector<char>> visited(m,vector<char>(n,'0'));
        int res=false;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==word[0]){
                    res=dfs(board,word,visited,0,i,j);
                    if(res)
                        return res;
                }
            }
        }
        return res;
    }
};
